#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) { val = x; left = right = nullptr; }
};

class Solution {
public:
    int TreeLeft(TreeNode* root)
    {
        if (root == nullptr)
            return 0;

        return root->val + TreeLeft(root->left) + TreeRight(root->right);
    }
    int TreeRight(TreeNode* root)
    {
        if (root == nullptr)
            return 0;

        return root->val + TreeLeft(root->left) + TreeRight(root->right);
    }
    void _findTilt(TreeNode* root)
    {
        if (root == nullptr)
            return;

        int left = TreeLeft(root->left);
        int right = TreeRight(root->right);
        root->val = abs(left - right);

        _findTilt(root->left);
        _findTilt(root->right);
    }

    int sumTilt(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        return root->val + sumTilt(root->left) + sumTilt(root->right);
    }

    int findTilt(TreeNode* root) {
        _findTilt(root);
        return sumTilt(root);
    }
};

int main()
{
    TreeNode t1(4);
    TreeNode t2(2);
    TreeNode t3(3);
    TreeNode t4(5);
    TreeNode t5(9);
    TreeNode t6(7);
    t1.left = &t2;
    t1.right = &t5;
    t2.left = &t3;
    t2.right = &t4;
    t5.right = &t6;

    Solution s;
    cout << s.findTilt(&t1) << endl;

    return 0;
}